// 滑动窗口
// 利用 单调性， 使用 同向双指针 的方法进行优化，使得时间复杂度降低 O(N)
// 定义 双指针 用于维护 窗口 的左右边界
// 进窗口 -> 判断是否出窗口，过程中统计结果

// 例题 1：
// 给定一个含有 n 个正整数的数组和一个正整数 target 。
//
//        找出该数组中满足其总和大于等于 target 的长度最小的子数组
//        [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

//        示例 1：
//
//        输入：target = 7, nums = [2,3,1,2,4,3]
//        输出：2
//        解释：子数组 [4,3] 是该条件下的长度最小的子数组。
//        示例 2：
//
//        输入：target = 4, nums = [1,4,4]
//        输出：1
//        示例 3：
//
//        输入：target = 11, nums = [1,1,1,1,1,1,1,1]
//        输出：0
//
//
//        提示：
//
//        1 <= target <= 109
//        1 <= nums.length <= 105
//        1 <= nums[i] <= 104

// 解题思路：
// 进窗口：sum += nums[left]
// 当 sum > target，出窗口：sum -= nums[left] left++

public class MinSubArrayLen {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        int sum  = 0;
        int ret = Integer.MAX_VALUE;
        while(right < n){
            sum += nums[right];
            while(sum >= target){
                ret = Math.min(ret, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }
}
